/**
 * 203.移除链表元素
 * 206.反转链表
 * 24.两两交换链表中的节点
 * 19.删除链表的倒数第N个节点
 * 
 * 链表常用技巧：哑结点，快慢指针
 * 迭代+递归
 * **/

#include <iostream>
using namespace std;

struct ListNode {
    ListNode(int val = 0, ListNode *next = nullptr)
        : val(val), next(next) {}
    int val;
    ListNode *next;
};

class Solution
{
public:
    // 203. 递归
    ListNode *removeElements(ListNode *head, int val)
    {
        // 递归
        if (head == nullptr) {
            return nullptr;
        }
        head->next = removeElements(head->next, val);
        if (head->val == val) {
            return head->next;
        }
        return head;
    }
    // 203. 迭代
    ListNode *removeElements2(ListNode *head, int val)
    {
        ListNode dummy = ListNode(); // 使用栈空间，无需考虑free
        dummy.next = head;
        ListNode *pre = &dummy, *cur = dummy.next;
        while (cur != nullptr) {
            if (cur->val == val) {
                pre->next = cur->next;
            } else {
                pre = cur;
            }
            cur = cur->next;
        }
        return dummy.next;
    }
    // 206. 递归
    ListNode *reverseList(ListNode *head)
    {
        // 递归
        // 出口：链表就一个节点时天然逆序
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode *newHead = reverseList(head->next);
        // head 1->2<-3<-4<-5 newHead
        //         NULL
        // head->next即指向2，1->2还没断开
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
    // 206. 迭代 三指针
    ListNode *reverseList2(ListNode *head)
    {
        // 迭代借助三指针
        ListNode *pre = nullptr;
        // 原链表必被破坏，无需用cur=head了
        while (head != nullptr) {
            ListNode *post = head->next;
            head->next = pre;
            pre = head;
            head = post;
        }
        // head == nullptr
        return pre;
    }
    // 24. 迭代
    ListNode *swapPairs2(ListNode *head)
    {
        ListNode dummy = ListNode(0, head);
        ListNode *cur = &dummy;
        while (cur->next != nullptr && cur->next->next != nullptr) {
            ListNode *one = cur->next;
            ListNode *three = cur->next->next->next;
            cur->next = one->next; // dummy->2
            one->next->next = one; // 2->1
            one->next = three;     //1->3
            cur = cur->next->next;
        }
        return dummy.next;
    }
    // 24. 递归
    ListNode *swapPairs(ListNode *head)
    {
        // 递归
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode *post = head->next;
        head->next = swapPairs(head->next->next);
        post->next = head;
        return post;
    }
    // 19.
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode dummy = ListNode(0, head);
        ListNode *fast = &dummy, *slow = &dummy;
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        // fast指向最后一个节点，slow指向要删除的前驱节点
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummy.next;
    }
};